//
// Created by Administrator on 2020/11/4.
//

#ifndef DFS_AND_COMPONENTS_COMPONENTS_H
#define DFS_AND_COMPONENTS_COMPONENTS_H

#include <iostream>
#include <cassert>
using namespace std;

template <typename Graph>
class Components {
private:
    Graph &G;
    bool *visited;
    int ccount;
    int *id;

    void dfs(int v){
        visited[v] = true;
        id[v] = ccount;
        // 编译器无法判断是Graph的一个类型还是一个成员变量，需加关键字typename
        typename Graph::adjIterator adj(G, v);
        for(int i = adj.begin(); !adj.end(); i = adj.next()){
            if(!visited[i])
                dfs(i);
        }
    }
public:
    Components(Graph &graph): G(graph){
        visited = new bool[G.V()];
        id = new int[G.V()];
        ccount = 0;
        // 初始化
        for(int i = 0; i < G.V(); ++i){
            visited[i] = false;
            id[i] = -1;
        }
        for(int i = 0; i < G.V(); ++i){
            if(!visited[i]){
                dfs(i);
                ccount++;
            }
        }
    }
    ~Components(){
        delete[] visited;
        delete[] id;
    }
    int count(){
        return ccount;
    }
    // 查询两个节点是否相连
    bool isConnected(int v, int w){
        assert(v >= 0 && v < G.V());
        assert(w >= 0 && w < G.V());
        return id[v] == id[w];
    }
};



#endif //DFS_AND_COMPONENTS_COMPONENTS_H
